<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/%E6%AD%A6%E6%B1%8932x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/%E6%AD%A6%E6%B1%8916x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib1/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/lib1/pace/pace-theme-center-simple.min.css">
  <script src="/lib1/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"example.com","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="前言数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 程序设计 &#x3D; 数据结构 + 算法。 数据结构可以分为逻辑结构与物理结构。 逻辑结构：是指数据对象中数据元素之间的相互关系；可分为以下四种： 集合结构：集合结构中的数据元素处理同属于一个集合外，并无其他关系。线性结构：线性结构中数据元素为一对一的关系。树形结构：一对多的层次关系。图形结构：多对多的关系。 物理结构：是指数据的逻辑结构在">
<meta property="og:type" content="article">
<meta property="og:title" content="大话数据结构">
<meta property="og:url" content="http://example.com/2021/09/28/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/index.html">
<meta property="og:site_name" content="Technological Blog">
<meta property="og:description" content="前言数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 程序设计 &#x3D; 数据结构 + 算法。 数据结构可以分为逻辑结构与物理结构。 逻辑结构：是指数据对象中数据元素之间的相互关系；可分为以下四种： 集合结构：集合结构中的数据元素处理同属于一个集合外，并无其他关系。线性结构：线性结构中数据元素为一对一的关系。树形结构：一对多的层次关系。图形结构：多对多的关系。 物理结构：是指数据的逻辑结构在">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2021-09-28T04:18:39.000Z">
<meta property="article:modified_time" content="2021-11-03T08:28:22.705Z">
<meta property="article:author" content="Li Yudong">
<meta property="article:tag" content="设计模式">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="http://example.com/2021/09/28/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>大话数据结构 | Technological Blog</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Technological Blog</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">IT小白的成长之旅</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="tags fa-fw"></i>标签<span class="badge">18</span></a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="th fa-fw"></i>分类<span class="badge">14</span></a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档<span class="badge">95</span></a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

  <a href="https://github.com/tiarmor1" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://example.com/2021/09/28/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/author.jpg">
      <meta itemprop="name" content="Li Yudong">
      <meta itemprop="description" content="">
    </span>
    
    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Technological Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          大话数据结构
        </h1>
    
        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
    
              <time title="创建时间：2021-09-28 12:18:39" itemprop="dateCreated datePublished" datetime="2021-09-28T12:18:39+08:00">2021-09-28</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-11-03 16:28:22" itemprop="dateModified" datetime="2021-11-03T16:28:22+08:00">2021-11-03</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" itemprop="url" rel="index"><span itemprop="name">设计模式</span></a>
                </span>
            </span>
    
          
    
        </div>
      </header>
    
    
    
    
    <div class="post-body" itemprop="articleBody">
    
      
        <h1 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h1><p>数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。</p>
<p>程序设计 = 数据结构 + 算法。</p>
<p>数据结构可以分为逻辑结构与物理结构。</p>
<p>逻辑结构：是指数据对象中数据元素之间的相互关系；可分为以下四种：</p>
<p>集合结构：集合结构中的数据元素处理同属于一个集合外，并无其他关系。线性结构：线性结构中数据元素为一对一的关系。树形结构：一对多的层次关系。图形结构：多对多的关系。</p>
<p>物理结构：是指数据的逻辑结构在计算机中的存储形式。</p>
<p>物理结构分为：顺序存储结构、链式存储结构。</p>
<h1 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h1><p>线性表：零个或者多个数据元素的有限序列。</p>
<h2 id="顺序存储结构"><a href="#顺序存储结构" class="headerlink" title="顺序存储结构"></a>顺序存储结构</h2><p>线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。</p>
<p>顺序存储结构类似于数组的结构，其地址的计算方法跟元素的index序号，以及首元素的地址数组头地址均相关。</p>
<p>线性表的顺序存储结构，存、读数据的时间复杂度均为O(1)；而插入、删除的时间复杂度均为O(n)。</p>
<p>优点：1、无须为表示表内元素的逻辑关系，而额外增加存储空间；2、可快速存取表内任一位置元素；</p>
<p>缺点：1、插入和删除操作需要移动大量元素；2、当线性表长度变化较大时，难以确定存储空间的容量；3、容易造成存储空间的碎片。</p>
<h2 id="链式存储结构"><a href="#链式存储结构" class="headerlink" title="链式存储结构"></a>链式存储结构</h2><p>正是由于顺序存储结构的不足，因此诞生了链式存储结构。</p>
<p>在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址，分为数据域与指针域。对于单链表，通常为了操作的方便，我们会自己创建一个头指针与头节点来放在链表的最前面。</p>
<h3 id="循环链表"><a href="#循环链表" class="headerlink" title="循环链表"></a>循环链表</h3><p>将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环，这个头尾相接的链表称为循环链表。</p>
<h3 id="双向链表"><a href="#双向链表" class="headerlink" title="双向链表"></a>双向链表</h3><p>双向链表是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。</p>
<h1 id="栈与队列"><a href="#栈与队列" class="headerlink" title="栈与队列"></a>栈与队列</h1><h2 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h2><p>栈<strong>stack</strong>是限定仅在表尾进行插入和删除操作的线性表；允许插入、删除的一端称为栈顶，简称LIFO结构。（Last In First Out）。push进栈，pop出栈。</p>
<h3 id="顺序存储结构-1"><a href="#顺序存储结构-1" class="headerlink" title="顺序存储结构"></a>顺序存储结构</h3><p>其实就是线性表顺序存储的简化版，一般用数组来实现。同时，可以有多个栈来共享空间的操作。</p>
<h3 id="链式存储结构-1"><a href="#链式存储结构-1" class="headerlink" title="链式存储结构"></a>链式存储结构</h3><p>栈只用栈顶来做插入和删除操作，用于单链表有头指针，而栈顶指针也是必须的，因此其实可以合二为一。</p>
<h3 id="应用"><a href="#应用" class="headerlink" title="应用"></a>应用</h3><p>递归：我们把一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称为递归函数。递归的关键在于其推出条件，每个递归至少规定一个条件，满足时递归不再进行，即不引用自身而是返回值退出。</p>
<p>它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合。</p>
<p>递归的关键：递归关系与递归终止条件。（其他的扔给递归）</p>
<p>1、找整个递归的终止条件：递归应该在什么时候结束？</p>
<p>2、找返回值：应该给上一级返回什么信息？</p>
<p>3、本级递归应该做什么：在这一级递归中，应该完成什么任务？</p>
<p>迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。</p>
<p>递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换.能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。</p>
<p>逆波兰表达式：其实就是后缀表达式。例如：”9 + (3 - 1) * 3 + 10 ➗ 2”。用后缀表达式为”9 3 1 - 3 * + 10 2 / +”。</p>
<p>规则：从左往右遍历表达式的每个数字和符号，遇到数字则先进栈，遇到符号，则将处于栈顶的两个数字出栈，进行运算，并将运算结果入栈；一直到最终获得结果。</p>
<p>下面的代码用栈实现：由逆波兰表达式来求值。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">&#123;string[]&#125;</span> <span class="variable">tokens</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">&#123;number&#125;</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> evalRPN = <span class="function"><span class="keyword">function</span> (<span class="params">tokens</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">const</span> calculate = <span class="function">(<span class="params">num1, num2, operator</span>) =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">switch</span> (operator) &#123;</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"+"</span>:</span><br><span class="line">        <span class="keyword">return</span> num1 + num2;</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"-"</span>:</span><br><span class="line">        <span class="keyword">return</span> num1 - num2;</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"*"</span>:</span><br><span class="line">        <span class="keyword">return</span> num1 * num2;</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"/"</span>:</span><br><span class="line">        <span class="comment">// js 这里要用parseInt</span></span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">parseInt</span>(num1 / num2, <span class="number">10</span>);</span><br><span class="line">      <span class="keyword">default</span>:</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;;</span><br><span class="line">  <span class="keyword">let</span> stack = <span class="keyword">new</span> <span class="built_in">Array</span>();</span><br><span class="line">  <span class="keyword">for</span> (<span class="keyword">let</span> a <span class="keyword">of</span> tokens) &#123;</span><br><span class="line">    <span class="keyword">switch</span> (a) &#123;</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"+"</span>:</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"-"</span>:</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"*"</span>:</span><br><span class="line">      <span class="keyword">case</span> <span class="string">"/"</span>:</span><br><span class="line">        <span class="keyword">let</span> num1 = stack.pop();</span><br><span class="line">        <span class="keyword">let</span> num2 = stack.pop();</span><br><span class="line">        <span class="comment">// 注意下面调用calculate函数时第一个参数是num2而非num1</span></span><br><span class="line">        stack.push(calculate(num2, num1, a));</span><br><span class="line">        <span class="keyword">break</span>;</span><br><span class="line">      <span class="keyword">default</span>:</span><br><span class="line">        stack.push(<span class="built_in">parseInt</span>(a, <span class="number">10</span>));</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> stack.pop();</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>下面的代码使用两个栈将常用的中缀表达式转变为逆波兰表达式。</p>
<p>规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级不高于</p>
<p>1、创建两个栈s1，s2；s1用来存储运算符；s2用来存储中间结果</p>
<p>2、遍历表达式：当遇到数字时，推入s2</p>
<p>当遇到运算符时：若s1为空，或s1栈顶非运算符即 ( 和 ) ，推入s1；</p>
<p>与s1栈顶运算符比较：低于栈顶：推入s1；等于栈顶：推入s2；高于栈顶：弹出栈顶，将栈顶推入s2，循环直到该运算符弹入任意栈</p>
<p>3、处理 ( 和 )：</p>
<p>如果为 (，推入s1；如果为 ) ，将s1的栈顶不断的出栈并入栈到s2中，直到s1栈顶为 ( 时停止，并将 ( 出栈丢弃；</p>
<p>重复 2 里面的所有过程，直到表达式遍历结束；</p>
<p>将s2中的栈顶依次出栈并入栈到s1中；</p>
<p>将s1中的栈顶依次出栈并输出，即得到后缀表达式（逆波兰式）</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">infixToSuffix</span>(<span class="params">infix</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">let</span> symbol = [],</span><br><span class="line">    value = [],</span><br><span class="line">    res = <span class="string">''</span></span><br><span class="line">  infix.split(<span class="string">''</span>).forEach(<span class="function">(<span class="params">item</span>) =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">switch</span> (<span class="literal">true</span>) &#123;</span><br><span class="line">      <span class="keyword">case</span> <span class="regexp">/\d/</span>.test(item):</span><br><span class="line">        value.push(item)</span><br><span class="line">        <span class="keyword">break</span></span><br><span class="line">      <span class="keyword">case</span> <span class="regexp">/[+\-*/]/</span>.test(item):</span><br><span class="line">        <span class="keyword">while</span> (symbol.length + <span class="number">1</span>) &#123;</span><br><span class="line">          <span class="keyword">if</span> (!symbol.length || !<span class="regexp">/[+\-*/]/</span>.test(symbol[symbol.length - <span class="number">1</span>])) &#123;</span><br><span class="line">            <span class="comment">// 栈顶为空或非运算符</span></span><br><span class="line">            symbol.push(item) <span class="comment">// 弹入栈1</span></span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">          &#125;</span><br><span class="line">          <span class="keyword">if</span> (<span class="regexp">/[*/]/</span>.test(item) &amp;&amp; <span class="regexp">/[+\-]/</span>.test(symbol[symbol.length - <span class="number">1</span>])) &#123;</span><br><span class="line">            <span class="comment">// 比栈顶低</span></span><br><span class="line">            symbol.push(item) <span class="comment">// 弹入栈1</span></span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">          &#125;</span><br><span class="line">          <span class="keyword">if</span> (<span class="regexp">/[+\-]/</span>.test(item) &amp;&amp; <span class="regexp">/[*/]/</span>.test(symbol[symbol.length - <span class="number">1</span>])) &#123;</span><br><span class="line">            <span class="comment">// 比栈顶高</span></span><br><span class="line">            value.push(symbol.pop()) <span class="comment">// 弹出栈顶，栈顶弹入栈2</span></span><br><span class="line">            <span class="keyword">continue</span></span><br><span class="line">          &#125;</span><br><span class="line">          <span class="comment">// 等于栈顶</span></span><br><span class="line">          value.push(item) <span class="comment">// 弹入栈2</span></span><br><span class="line">          <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">break</span></span><br><span class="line">      <span class="keyword">case</span> <span class="regexp">/\(/</span>.test(item):</span><br><span class="line">        symbol.push(item)</span><br><span class="line">        <span class="keyword">break</span></span><br><span class="line">      <span class="keyword">case</span> <span class="regexp">/\)/</span>.test(item):</span><br><span class="line">        <span class="keyword">while</span> (symbol.length) &#123;</span><br><span class="line">          <span class="keyword">let</span> mid = symbol.pop()</span><br><span class="line">          <span class="keyword">if</span> (mid !== <span class="string">'('</span>) &#123;</span><br><span class="line">            value.push(mid)</span><br><span class="line">          &#125; <span class="keyword">else</span> <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">break</span></span><br><span class="line">      <span class="keyword">default</span>:</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;)</span><br><span class="line">  <span class="keyword">while</span> (value.length) &#123;</span><br><span class="line">    symbol.push(value.pop())</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">while</span> (symbol.length) &#123;</span><br><span class="line">    res += symbol.pop()</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line"><span class="built_in">console</span>.log(infixToSuffix(<span class="string">'(3+4)*5-6'</span>)) <span class="comment">// 34+5*6-</span></span><br><span class="line"><span class="built_in">console</span>.log(infixToSuffix(<span class="string">'1+2*3+(4*5+6)*7'</span>)) <span class="comment">// 123*+45*6+7*+</span></span><br></pre></td></tr></table></figure>

<h2 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h2><p>队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出的线性表FIFO。允许插入的一端成为队尾，允许删除的一段称为队头。</p>
<p>循环队列：队列的头尾相连的顺序存储结构称为循环队列。循环队列使得队头和队尾</p>
<p>队列的链式存储结构，其实就是线性表的单链表。</p>
<h2 id="串"><a href="#串" class="headerlink" title="串"></a>串</h2><p>串是由零个或者多个字符组成的有限序列，又名叫字符串。</p>
<p>串的模式匹配：定位子串在主串中的位置。最快速的算法是KMP模式匹配算法。</p>
<p>KMP算法的关键在于其next数组的选取与推导。</p>
<h3 id="KMP算法"><a href="#KMP算法" class="headerlink" title="KMP算法"></a>KMP算法</h3><h1 id="树"><a href="#树" class="headerlink" title="树"></a>树</h1><p>树本身其实就是一个递归的定义。1、树的根节点是唯一的，不可能出现多个根节点。2、子树的个数没有限制，但它们一定是互不相交的。</p>
<p>树的结点包括一个数据元素与若干指向其子树的分支。结点拥有的子树数称为结点的度degree。度为0的结点称为叶结点或者终端结点。</p>
<p>如果将树中所有结点的各个子树看作从左到右是有次序的，不能互换的，则称该树为有序树，否则为无序树。</p>
<p>满二叉树：一个二叉树如果所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。</p>
<p>完全二叉树：对一棵具有n个结点的二叉树按照层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点位置完全相同，则该二叉树称为完全二叉树。</p>
<p>完全二叉树的特点：1、叶子结点只出现在最后两层，2、最下层结点一定位于左部连续位置，3、倒数第二层，若有叶子节点，一定位于右部连续位置；4、若结点度为1，则只有左孩子，无右孩子；5、同样结点树的二叉树，完全二叉树深度最小。</p>
<h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><h3 id="二叉树性质"><a href="#二叉树性质" class="headerlink" title="二叉树性质"></a>二叉树性质</h3><p>1、在二叉树的第i层上至多有2^（i-1）个结点；</p>
<p>2、深度为k的二叉树至多有2^k - 1个结点；</p>
<p>3、对任何一棵二叉树T，如果其终端结点数为n，度为2的结点数为m，则n = m + 1；（终端结点数其实就是叶子结点数）。推论方式：总结点数all = n + m + l；l是度为1的结点数。同理，根据连线数可知，由于根节点只有分支出去，没有分支进入，所以分支线总数为结点总数-1= all - 1。而分支线总数又等于l + 2m。因此n + m + l - 1= l + 2m。n = m + 1。</p>
<p>4、具有n个结点的完全二叉树的深度为log2n + 1。通过深度k的完全二叉树结点数反推即可。</p>
<p>5、如果对一棵有n个结点的完全二叉树的结点按层序编号，对于任一结点有：</p>
<p>i=1时，则结点i为二叉树的根，无双亲；如果i &gt; 1，则其双亲是结点 i/2。</p>
<p>如果2i &gt; n，则结点i无左孩子；否则其左孩子为结点2i</p>
<p>如果2i+1 &gt; n，则结点i无右孩子；否则其右孩子为结点2i + 1。</p>
<p>这个性质在堆排序中十分常见，用于寻找结点的双亲结点。</p>
<h3 id="存储结构"><a href="#存储结构" class="headerlink" title="存储结构"></a>存储结构</h3><p>二叉树的顺序存储结构通常用数组来实现，通过数组的下标来体现结点之间的逻辑关系。通常这种情况用于二叉堆比较多，堆排序其实就是这样的思路。</p>
<p>二叉链表：二叉树的每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是自然的想法。</p>
<h3 id="遍历"><a href="#遍历" class="headerlink" title="遍历"></a>遍历</h3><h4 id="前、中、后序遍历"><a href="#前、中、后序遍历" class="headerlink" title="前、中、后序遍历"></a>前、中、后序遍历</h4><p>前序遍历的代码如下：包括递归实现与迭代实现。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//递归实现如下</span></span><br><span class="line"><span class="keyword">const</span> preorderTraversal = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line">    <span class="comment">//定义一个数组存储遍历结果</span></span><br><span class="line">    <span class="keyword">const</span> traversal = <span class="function">(<span class="params">root</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="comment">//定义递归函数，用于前序遍历每一轮二叉树</span></span><br><span class="line">        <span class="keyword">if</span> (root !== <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="comment">//递归的关键：退出条件-节点为空</span></span><br><span class="line">            res.push(root.val);</span><br><span class="line">            traversal(root.left);</span><br><span class="line">            traversal(root.right);</span><br><span class="line">            <span class="comment">//依次递归遍历左右子树</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    traversal(root);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*迭代的实现如下，维护一个栈来实现先序遍历</span></span><br><span class="line"><span class="comment">首先根入栈将根节点出栈，将根节点值放入结果数组中</span></span><br><span class="line"><span class="comment">然后遍历左子树、右子树，因为栈是先入后出，所以，我们先右子树入栈，然后左子树入栈</span></span><br><span class="line"><span class="comment">继续出栈（左子树被出栈）</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">const</span> preorderTraversal = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line">    <span class="keyword">const</span> stack = [];</span><br><span class="line">    <span class="keyword">let</span> node = root;</span><br><span class="line">    <span class="comment">//类似于链表中定义头节点的行为，后续用node进行指针遍历操作</span></span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span> (node || stack.length) &#123;</span><br><span class="line">        <span class="comment">//只有node为空，且栈内值均出栈时，整个迭代流程才结束</span></span><br><span class="line">        <span class="keyword">if</span> (node) &#123;</span><br><span class="line">            <span class="comment">//向左一直找到最下方的左叶子节点</span></span><br><span class="line">            res.push(node.val);</span><br><span class="line">            stack.push(node.right);</span><br><span class="line">            stack.psuh(node.left);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            node = stack.pop();</span><br><span class="line">            <span class="comment">//当找到最下方的左叶子节点时，则栈顶结点出栈，作为node继续迭代。</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>中序遍历的代码如下：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> inorderTraversal = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = []</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">traversal</span> (<span class="params">root</span>) </span>&#123;</span><br><span class="line">      <span class="keyword">if</span> (root !== <span class="literal">null</span>) &#123;</span><br><span class="line">        traversal(root.left)</span><br><span class="line">        res.push(root.val)</span><br><span class="line">        traversal(root.right)</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    traversal(root)</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">  &#125;</span><br><span class="line"><span class="comment">/*同样可以通过维护一个栈来使用迭代算法，从而实现二叉树的中序遍历 </span></span><br><span class="line"><span class="comment">1、每次先看node结点存在与否，存在则入栈，并跳左结点，从而先遍历左子树；</span></span><br><span class="line"><span class="comment">2、直到node结点不存在时，则出栈上一个作为node，此时代表左子树已经全部遍历完成，则需要将跟结点值放入结果数组，并跳右节点，遍历右子树</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">var</span> inorderTraversal = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line">    <span class="keyword">const</span> stack = [];</span><br><span class="line">    <span class="keyword">let</span> node = root;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (node || stack.length) &#123;</span><br><span class="line">        <span class="keyword">if</span> (node) &#123;</span><br><span class="line">            <span class="comment">//存在node结点，则先入栈并跳左结点，从而遍历左子树</span></span><br><span class="line">            stack.push(node);</span><br><span class="line">            node = node.left;</span><br><span class="line">            <span class="comment">//遍历左边的子树,每次只入栈一个node即可</span></span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//node不存在时，则左子树遍历完成，结点值放入结果，跳右节点，从而遍历右子树。</span></span><br><span class="line">            node = stack.pop();</span><br><span class="line">            res.push(node.val);</span><br><span class="line">            <span class="comment">//由于是中序遍历，</span></span><br><span class="line">            node = node.right;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>后序遍历的代码如下：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> postorderTraversal = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = []</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">traversal</span> (<span class="params">root</span>) </span>&#123;</span><br><span class="line">      <span class="keyword">if</span> (root !== <span class="literal">null</span>) &#123;</span><br><span class="line">        traversal(root.left)</span><br><span class="line">        traversal(root.right)</span><br><span class="line">        res.push(root.val)</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    traversal(root)</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*同样通过维护一个栈来使用迭代算法，从而实现二叉树的后序遍历</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">方法一：使用队列辅助迭代实现</span></span><br><span class="line"><span class="comment">解题思路： 后序遍历与前序遍历不同的是：</span></span><br><span class="line"><span class="comment">后序遍历是左右根</span></span><br><span class="line"><span class="comment">而前序遍历是根左右</span></span><br><span class="line"><span class="comment">如果我们把前序遍历的 list.push(node.val) 变更为 list.unshift(node.val) （遍历结果逆序），那么遍历顺序就由 根左右 变更为 右左根</span></span><br><span class="line"><span class="comment">然后我们仅需将 右左根 变更为 左右根 即可完成后序遍厉。</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">var</span> postorderTraversal = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line">    <span class="keyword">const</span> stack = [];</span><br><span class="line">    <span class="keyword">let</span> node = root;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (node || stack.length) &#123;</span><br><span class="line">        <span class="keyword">if</span> (node) &#123;</span><br><span class="line">            res.unshift(node.val);</span><br><span class="line">            stack.push(node.left);</span><br><span class="line">            node = node.right;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            node = stack.pop();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="BFS与DFS"><a href="#BFS与DFS" class="headerlink" title="BFS与DFS"></a>BFS与DFS</h4><p>层序遍历代码如下：层序遍历的本质其实就是二叉树的BFS，广度优先遍历。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">递归传递的参数除了头节点以外，一定要加上当前的层数，这样才能够正确地生成数组 </span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line">  <span class="keyword">var</span> levelOrder = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = []</span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">traversal</span> (<span class="params">root, depth</span>) </span>&#123;</span><br><span class="line">      <span class="keyword">if</span> (root !== <span class="literal">null</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span> (!res[depth]) &#123;</span><br><span class="line">          res[depth] = []</span><br><span class="line">        &#125;</span><br><span class="line">        traversal(root.left, depth + <span class="number">1</span>)</span><br><span class="line">        res[depth].push(root.val)</span><br><span class="line">        traversal(root.right, depth + <span class="number">1</span>)</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    traversal(root, <span class="number">0</span>)</span><br><span class="line">    <span class="keyword">return</span> res</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//迭代的代码实现方式如下：</span></span><br><span class="line"><span class="keyword">var</span> levelOrder = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="comment">//二叉树的层序遍历</span></span><br><span class="line">    <span class="keyword">let</span> res=[],queue=[];</span><br><span class="line">    queue.push(root);</span><br><span class="line">    <span class="keyword">if</span>(root===<span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(queue.length!==<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="comment">// 记录当前层级节点数</span></span><br><span class="line">        <span class="keyword">let</span> length=queue.length;</span><br><span class="line">        <span class="comment">//存放每一层的节点 </span></span><br><span class="line">        <span class="keyword">let</span> curLevel=[];</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>;i&lt;length;i++)&#123;</span><br><span class="line">            <span class="keyword">let</span> node=queue.shift();</span><br><span class="line">            curLevel.push(node.val);</span><br><span class="line">            <span class="comment">// 存放当前层下一层的节点</span></span><br><span class="line">            node.left &amp;&amp; queue.push(node.left);</span><br><span class="line">            node.right &amp;&amp; queue.push(node.right);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//把每一层的结果放到结果数组</span></span><br><span class="line">        res.push(curLevel);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>深度优先遍历DFS的代码如下：</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> dfs = <span class="function">(<span class="params">root</span>) =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (root == <span class="literal">null</span>)&#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    dfs(root.left);</span><br><span class="line">    dfs(root.right);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//下面是一个简单的全排列的代码，其实本质上就是一个回溯</span></span><br><span class="line"><span class="keyword">var</span> permute = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> res = [];</span><br><span class="line">    <span class="comment">//递归的关键：递归关系与递归终止条件。（其他的扔给递归）</span></span><br><span class="line">    <span class="comment">//1、找整个递归的终止条件：递归应该在什么时候结束？</span></span><br><span class="line">    <span class="comment">//2、找返回值：应该给上一级返回什么信息？</span></span><br><span class="line">    <span class="comment">//3、本级递归应该做什么：在这一级递归中，应该完成什么任务？</span></span><br><span class="line">    <span class="comment">//本题中，应当传递给递归的参数最少可以只有1个，但用一个map或数组去记录已加入路径的数字，</span></span><br><span class="line">    <span class="comment">//而不是调用 path.includs 类似的库函数，导致每次都是 O(n) 的查找时间。</span></span><br><span class="line">    <span class="keyword">const</span> dfs = <span class="function">(<span class="params">path, set</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (path.length === nums.length) &#123;</span><br><span class="line">            res.push(path.slice());</span><br><span class="line">            <span class="keyword">return</span>;<span class="comment">//由于数组是引用类型，因此每次返回必须返回新的数组，避免后续修改bfs对当前返回造成的影响</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i &lt; nums.length; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (!<span class="keyword">set</span>[i]) &#123;</span><br><span class="line">                path.push(nums[i]);</span><br><span class="line">                <span class="keyword">set</span>[i] = true;</span><br><span class="line">                dfs(path, <span class="keyword">set</span>);</span><br><span class="line"></span><br><span class="line">                //回溯</span><br><span class="line">                path.pop();</span><br><span class="line">                <span class="keyword">set</span>[i] = false;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    dfs([], []);</span><br><span class="line"></span><br><span class="line">    return res;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>下面是一个获取二叉树所有的路径的题目，本质上也是一个二叉树的DFS遍历</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> binaryTreePaths = <span class="function"><span class="keyword">function</span>(<span class="params">root</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">const</span> paths = [];</span><br><span class="line">    <span class="keyword">const</span> construct_paths = <span class="function">(<span class="params">root, path</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (root) &#123;</span><br><span class="line">            <span class="comment">//递归的结束条件是root为空</span></span><br><span class="line">            path += root.val.toString();</span><br><span class="line">            <span class="keyword">if</span> (root.left === <span class="literal">null</span> &amp;&amp; root.right === <span class="literal">null</span>) &#123;</span><br><span class="line">                <span class="comment">//即当前节点为叶子节点时,这是符合要求，路径到最后的条件</span></span><br><span class="line">                paths.push(path);<span class="comment">//则此时将路径进栈，再去找其他的路径。</span></span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                path += <span class="string">"-&gt;"</span>;<span class="comment">//当节点不是叶子节点时，继续进行递归遍历</span></span><br><span class="line">                construct_paths(root.left, path);</span><br><span class="line">                construct_paths(root.right, path);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    construct_paths(root, <span class="string">""</span>);</span><br><span class="line">    <span class="keyword">return</span> paths;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>下面是一个：二叉树的节点和为某一个值得路径。剑指offer34题，找出从根节点到叶子节点路径总和等于给定目标和得路径。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*代码本质上其实就是一个DFS+剪枝的过程</span></span><br><span class="line"><span class="comment">1、剪枝：空树时则返回；</span></span><br><span class="line"><span class="comment">2、由于路径要从根节点到叶子节点，因此符合要求的条件有：路径和+该点=target；左右子树均为空;</span></span><br><span class="line"><span class="comment">3、回溯代码的一般步骤：先处理节点，然后DFS，最后回溯。</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">const</span> pathSum = <span class="function"><span class="keyword">function</span>(<span class="params">root, target</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> res = [];</span><br><span class="line">    <span class="keyword">let</span> path = [];</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">function</span> <span class="title">DFS</span>(<span class="params">root, sum</span>) </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!root) <span class="keyword">return</span>; <span class="comment">//剪枝的条件为此时为空节点</span></span><br><span class="line">        <span class="keyword">if</span> (!root.left &amp;&amp; !root.right &amp;&amp; (sum + root.val == target)) &#123;</span><br><span class="line">            res.push([...path, root.val]);</span><br><span class="line">            <span class="keyword">return</span> ;</span><br><span class="line">        &#125;</span><br><span class="line">        path.push(root.val);</span><br><span class="line">        DFS(root.left, sum + root.val);</span><br><span class="line">        DFS(root.right, sum + root.val);</span><br><span class="line">        path.pop();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>

<p>leetcode124题：二叉树中的最大路径和。</p>
<p>这个路径被定义为一条从树中任一节点触发，沿父节点-子节点连接，达到任意节点的序列。</p>
<p>思路：1、路径走到一个节点，有三个选择，停下、走左结点、走右节点。递归很容易来解决这种重复性问题。注意：不能回头走分支，因为路径不能重叠。</p>
<p>定义递归函数：对于一个父节点，它关心自己走入一个子树，从中捞取的最大收益，不关心具体怎么走。</p>
<p>DFS：返回当前子树能向父节点提供的最大路径和，即Max(root.val, root.val + dfs(root.left), root.val + dfs(root.right))。即三种情况的最大值。</p>
<p>注意项：1、不能回头，导致路径重叠；2、遍历至null时，返回。3、若某个子树DFS结果为负，则直接排除。</p>
<p>一个子树内部最大路径和 = 左子树提供最大子树和 + 根节点 + 右子树最大路径和</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">const</span> maxPathSum = <span class="function">(<span class="params">root</span>) =&gt;</span> &#123;</span><br><span class="line">    <span class="keyword">let</span> maxSum = <span class="built_in">Number</span>.MIN_SAFE_INTEGER;</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">const</span> dfs = <span class="function">(<span class="params">root</span>) =&gt;</span> &#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="literal">null</span>) &#123;</span><br><span class="line">            <span class="comment">//遍历到null节点时，收益为0</span></span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">const</span> left = dfs(root.left);<span class="comment">//左子树提供的最大路径和</span></span><br><span class="line">        <span class="keyword">const</span> right = dfs(root.right);</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">const</span> innnerMaxSum = left + root.val + right;<span class="comment">//当前子树内部的最大路径和</span></span><br><span class="line">        maxSum = <span class="built_in">Math</span>.max(maxSum, innerMaxSum);</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">const</span> outputMaxSum = root.val + <span class="built_in">Math</span>.max(<span class="number">0</span>, left, right);</span><br><span class="line">        </span><br><span class="line">        <span class="keyword">return</span> outputMaxSum &lt; <span class="number">0</span> ? <span class="number">0</span> : outputMaxSum;</span><br><span class="line">    &#125;;</span><br><span class="line">    </span><br><span class="line">    dfs(root);</span><br><span class="line">    <span class="keyword">return</span> maxSum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="线索二叉树"><a href="#线索二叉树" class="headerlink" title="线索二叉树"></a>线索二叉树</h3><p>我们把这种指向前驱和后继的指针称为线索，而加上线索的二叉链表称为线索链表；相应的二叉树就称为线索二叉树。</p>
<p>我们对二叉树以某种次序遍历使其变成线索二叉树的过程，称为线索化。</p>
<h2 id="赫夫曼树"><a href="#赫夫曼树" class="headerlink" title="赫夫曼树"></a>赫夫曼树</h2><p>路径长度：从树中一个结点到另一个结点之间的分支，构成两个结点之间的路径，路径上的分支数目称作路径长度。</p>
<p>而树本身的路径长度就是：树根节点到每一个结点的路径长度之和。</p>
<p>如果对路径长度与结点都加上权值的话，带权路径长度WPL，WPL最小的二叉树称作赫夫曼树，又叫最优二叉树。</p>
<p>构造赫夫曼树的赫夫曼算法描述如下：</p>
<p>1、根据给定的n个权值{W1, W2, W3,…,Wn}构成n棵二叉树的集合F={T1,T2, … Tn},其中每棵二叉树Ti中只有一个带权为Wi根节点，其左右子树均为空。</p>
<p>2、在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新得二叉树的根节点的权值为其左右子树上根节点的权值之和。</p>
<p>3、在F中删除这两棵树，同时将新得到的二叉树加入F中。</p>
<p>4、重复2、3步骤，直至F只含一棵树为止，这棵树就是赫夫曼树。</p>
<h1 id="图"><a href="#图" class="headerlink" title="图"></a>图</h1><p>图是一种相较于线性表与树，更加复杂的数据结构，在图形的结构中，结点之间的关系可以是任意的，图中任何两个数据元素之间都可能相关。</p>
<p>图中的数据元素称为顶点，而图中的连接线分为无向边与有向边，同样图按照有无方向可分为有向图与无向图。</p>
<p>图的存储结构：邻接矩阵与邻接表。</p>

    </div>
    
    
    
    
    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
    
</div>

      
    </div>
        <div class="reward-container">
  <div>坚持原创技术分享，您的支持将鼓励我继续创作！</div>
  <button onclick="var qr = document.getElementById('qr'); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
      
      <div style="display: inline-block;">
        <img src="/images/alipay.png" alt="Li Yudong 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>

        

<div>
<ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>Li Yudong
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://example.com/2021/09/28/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E5%A4%A7%E8%AF%9D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" title="大话数据结构">http://example.com/2021/09/28/设计模式/大话数据结构/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

    
      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" rel="tag"># 设计模式</a>
          </div>
    
        

    
        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2021/09/25/node/node.js%E5%88%9D%E8%AF%86/" rel="prev" title="nodejs">
      <i class="fa fa-chevron-left"></i> nodejs
    </a></div>
      <div class="post-nav-item">
    <a href="/2021/09/30/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/%E6%9F%A5%E6%89%BE%E4%B8%8E%E6%8E%92%E5%BA%8F/" rel="next" title="查找与排序">
      查找与排序 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#前言"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#线性表"><span class="nav-number">2.</span> <span class="nav-text">线性表</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#顺序存储结构"><span class="nav-number">2.1.</span> <span class="nav-text">顺序存储结构</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#链式存储结构"><span class="nav-number">2.2.</span> <span class="nav-text">链式存储结构</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#循环链表"><span class="nav-number">2.2.1.</span> <span class="nav-text">循环链表</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#双向链表"><span class="nav-number">2.2.2.</span> <span class="nav-text">双向链表</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#栈与队列"><span class="nav-number">3.</span> <span class="nav-text">栈与队列</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#栈"><span class="nav-number">3.1.</span> <span class="nav-text">栈</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#顺序存储结构-1"><span class="nav-number">3.1.1.</span> <span class="nav-text">顺序存储结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#链式存储结构-1"><span class="nav-number">3.1.2.</span> <span class="nav-text">链式存储结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#应用"><span class="nav-number">3.1.3.</span> <span class="nav-text">应用</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#队列"><span class="nav-number">3.2.</span> <span class="nav-text">队列</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#串"><span class="nav-number">3.3.</span> <span class="nav-text">串</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#KMP算法"><span class="nav-number">3.3.1.</span> <span class="nav-text">KMP算法</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#树"><span class="nav-number">4.</span> <span class="nav-text">树</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#二叉树"><span class="nav-number">4.1.</span> <span class="nav-text">二叉树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#二叉树性质"><span class="nav-number">4.1.1.</span> <span class="nav-text">二叉树性质</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#存储结构"><span class="nav-number">4.1.2.</span> <span class="nav-text">存储结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#遍历"><span class="nav-number">4.1.3.</span> <span class="nav-text">遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#前、中、后序遍历"><span class="nav-number">4.1.3.1.</span> <span class="nav-text">前、中、后序遍历</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#BFS与DFS"><span class="nav-number">4.1.3.2.</span> <span class="nav-text">BFS与DFS</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#线索二叉树"><span class="nav-number">4.1.4.</span> <span class="nav-text">线索二叉树</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#赫夫曼树"><span class="nav-number">4.2.</span> <span class="nav-text">赫夫曼树</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图"><span class="nav-number">5.</span> <span class="nav-text">图</span></a></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Li Yudong"
      src="/images/author.jpg">
  <p class="site-author-name" itemprop="name">Li Yudong</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">95</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">14</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">18</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/tiarmor1" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;tiarmor1" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:1157019137@qq.com" title="E-Mail → mailto:1157019137@qq.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>
  <div class="cc-license motion-element" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2020 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Li Yudong</span>
</div>

        








      </div>
    </footer>
  </div>

  
  
  <script color='0,0,0' opacity='0.5' zIndex='-1' count='150' src="/lib1/canvas-nest/canvas-nest.min.js"></script>
  <script src="/lib1/anime.min.js"></script>
  <script src="/lib1/velocity/velocity.min.js"></script>
  <script src="/lib1/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  

  
   <canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
   <script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
   <script type="text/javascript" src="/js/fireworks.js"></script>
  
</body>
</html>

